Ad hoc networks are self-forming networks which can operate in the absence of any fixed infrastructure, and in some cases the ad hoc network is formed entirely of mobile nodes. An ad hoc network typically includes a number of geographically-distributed, potentially mobile units, sometimes referred to as “wireless device” or “nodes,” which are wirelessly connected to each other by one or more links (e.g., radio frequency communication channels). The nodes can communicate with each other over a wireless media without the support of an infrastructure-based or wired network. Links or connections between these nodes can change dynamically in an arbitrary manner as existing nodes move within the ad hoc network, as new nodes join or enter the ad hoc network, or as existing nodes leave or exit the ad hoc network.
One characteristic of ad hoc network nodes is that each node can directly communicate over a short range with nodes which are a single “hop” away. Such nodes are sometimes referred to as “neighbor nodes.” When a node transmits packets to a destination node and the nodes are separated by more than one hop (e.g., the distance between two nodes exceeds the radio transmission range of the nodes, or a physical barrier is present that limits the radio transmission range between the nodes), the packets can be relayed via intermediate relay nodes (“multi-hopping”) along a route until the packets reach the destination node. In such situations, each intermediate relay node routes the packets (e.g., data and control information) to the next node along the route, until the packets reach their final destination. For relaying packets to the next node, each node maintains routing information collected through communications with its neighboring nodes. The routing information can also be periodically broadcast in the network to reflect the current network topology. Alternatively, to reduce the amount of information transmitted for maintaining accurate routing information, the network nodes may exchange routing information only when it is needed. In many multi-hop ad hoc networks, multiple routes can be present between a source node and a destination node for communication of a particular data stream or “flow.”
Many ad hoc networks include one or more access points. An access point (AP) is a device communicatively connected either directly (via a wired link) or indirectly (via a wireless link) to a wired network that enables remote wireless nodes to communicate with the wired network (e.g. local area network (LAN), wide area network (WAN), etc.). An AP connects wireless communication devices which are in its direct communication range (i.e. one-hop away) together to form a wireless network. In many cases, the AP connects to a wired network, and can relay data between wireless devices and wired devices. For example, an AP can be a cellular base station such as implemented within IEEE 802.16 networks. (See: http://standards.ieee.org/getieee802/index.html or contact the IEEE at IEEE, 445 Hoes Lane, PO Box 1331, Piscataway, N.J. 08855-1331, USA.) In one implementation, an AP can be a Mesh Access Point (MAP) which has meshing capability. A MAP is distinguishable from a regular AP in that an MAP implements a mesh routing protocol such as a Mesh Scalable Routing (MSR) protocol disclosed in U.S. Pat. No. 7,061,925 B2, to Avinash Joshi, entitled “System and Method for Decreasing Latency in Locating Routes Between Nodes in a Wireless Communication Network,” its contents being incorporated by reference in its entirety herein. A MAP is also referred to as a “wireless device” or a “node”. An Intelligent Access Point (IAP) is a special MAP which connects to a wide area wired network (WAN) and can relay data between the wireless devices and the wired devices on the WAN. IAPs and MAPs can enable communication between the wired network and remote wireless nodes which are multi-hop away through the MSR and its proxy routing variant as disclosed in United States Patent Application Publication Number 20060098612, to Joshi et al, entitled “System and method for associating different types of nodes with access point nodes in a wireless network to route data in the wireless network”, and United States Patent Application Publication Number 20060098611, to Joshi et al, entitled “System and method for routing data between different types of nodes in a wireless network,” the contents of each being incorporated by reference herein.
A powered-on node can be in one of two possible states: an active state or a standby state. A node is in an active state when it is the source or destination of application data packets being communicated within a network. For example, a node is in an active state when it is on a voice-over-internet protocol (VOIP) call. When a node is not in an active state and is powered-on, it is in a standby state. For example, a node that is operated by a human user is in a standby state whenever its human user is not communicating using the node.
Mobile nodes are generally powered by batteries with a finite amount of energy. Batteries need to be recharged or replaced whenever their energy is exhausted. In order to extend the time between re-charges, it is beneficial to limit the power consumption of a node. A node consumes energy from its battery whenever it is powered on. A node in the active state generally consumes more energy than a node in the standby state. A standby-time is defined as the time between two consecutive battery recharges when the node is in the standby state.
Multi-hop communications, in general, require the various nodes to relay information from a source node to an AP. Given that the multi-hop relaying may require the participation of nodes that are in a standby state, one concern is how such multi-hop communications reduce the standby-time of user devices.
In order to include nodes in the standby state in the formation of multi-hop routes, it is necessary that nodes in the standby state periodically wake up to monitor a channel in which a routing message or a message indicating a route message can be transmitted. Such channel will be referred in this application as a “wake up channel”. The wake up channel may be a frequency channel, a period of time or time-slot, a specific spreading code or any combination of those that is specifically separated from the other channels for this purpose.
When a standby node wakes up in the wake up channel, other nodes may send a “remain awake” message in the wake up channel in order to request that node perform relay services to the AP or to other nodes within the network. When a standby node receives such “remain awake” messages, it remains awake for a period of time in order to exchange control messages to establish a final route to the destination.
The wake up channel may or may not be allocated at all times. For example, in systems employing a synchronous type of power save mode (PSM), the wake up channel is not allocated at all times; instead, it is allocated for just a period of time following the period in which system control information is transmitted in a beacon signal. Standby nodes wake up during a beacon period and a wake up period (the wake up channel); and, if they do not receive a “remain awake” message, they enter in a sleep state in between the end of the wake up period and the beginning of the next beacon. If standby nodes receive a “remain awake” message, they monitor other channels in which routing messages can be transmitted. A beacon is a unique message containing control information for the system. The beacon contains information such as synchronization information, paging information, network identification information, and the like. The purpose of the wake up channel is to allow active nodes to reach standby nodes to request relaying services. In other words, before a node sends a route discovery message to standby nodes, it requests that they remain awake by sending a “remain awake” message in the wake up channel.
While it is desirable to involve standby nodes in the formation of routes, it is also desirable to maximize the time in which a standby node is in the sleep state (i.e. to maximize its standby time). It is also desirable to minimize unnecessary activities in the standby node. Therefore, to balance all of these considerations, it is best to avoid standby nodes waking up when they are not needed and, when standby nodes are needed, it is necessary to provide a method to ensure that just the required quantity/subset of standby nodes wake up. Accordingly, there is a need for method and apparatus for controlling a wake up rate of nodes operating within a multi-hop communication system.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.
The apparatus and method components have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having the benefit of the description herein.